//
// Created by Lenovo on 2021/3/16.
//

#include "sort.h"
#include <iostream>
#include <vector>

using namespace std;

int getNumberByPos(int v, int pos) {
    while (pos-- > 0) {
        v = v / 10;
    }
    return v % 10;
}

/*
 *基数排序的思想：
 * 又称为桶排序，
 * 从个数开始，每次排序一个维度的数据，
 * 关键点，每一次排序，不影响上一次的排序结果，比如：10位排序，不影响个数排序结果。应为10位大的必然，值较大。
*/
void radixSort(int *list, int len) {
    for (int i = 0; i < 10; i++) {
        vector<vector<int>> bucket(10, vector<int>());
        for (int j = 0; j < len; j++) {
            int value = getNumberByPos(list[j], i);
            if (value != -1) {
                bucket[value].push_back(list[j]);
            }
        }

        int start = 0;
        for (vector<vector<int>>::iterator it = bucket.begin(); it != bucket.end(); it++) {
            vector<int> bucketSeg = *it;
            for (vector<int>::iterator it2 = bucketSeg.begin(); it2 != bucketSeg.end(); it2++) {
                list[start++] = *it2;
            }
        }
    }
}

